/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package compiler;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.Set;
import java.util.SortedSet;
import java.util.TreeSet;

import theory.DFA;

import compiler.parser.LALRParsingTable;
import compiler.parser.lalr.LALRState;
import compiler.parser.lalr.LALRUtils.Reduce;
import compiler.parser.lalr.LALRUtils.Shift;
import compiler.scanner.dfa.DFAState;
import compiler.scanner.nfa.ETransition;
import compiler.scanner.nfa.NFAState;
import compiler.scanner.nfa.NFATransition;

/**
 * 
 * @author meemo
 */
public class DotDump
{
    // ~ Methods ----------------------------------------------------------------

    public static String dumpDot(LALRParsingTable table)
    {
        StringBuilder sb = new StringBuilder();
        sb.append("digraph lalr {\n");

        boolean thisGrammarCanAccept = false; // if we have no accepting state, show an error
        int acceptingState = -1;

        for (int stateNo = 0; stateNo < table.getActionTable().length;
                 stateNo++)
        {
            String stateStr = "";
            boolean isAcceptingState = false;

            LALRState state = table.getState(stateNo);
            stateStr += state.toHTML();

            // processing action table (arrows with Terminals)
            String strArrow = "";

            boolean defaultActionDetected = false;

            if (table.getActionTable()[stateNo][table.getActionTable()[0].length - 1] instanceof Reduce)
            {
                defaultActionDetected = true;

                Reduce reduce = (Reduce)table.getActionTable()[stateNo][table.getActionTable()[0].length - 1];

                if ((table.getProductions().get(reduce.productionId)).getName() == null)
                {
                    isAcceptingState = true;
                    thisGrammarCanAccept = true;
                    acceptingState = stateNo;
                }

                // the accepting "augmenting" state can't have goto actions
                if ( !isAcceptingState)
                {
                    // default action is at the last index of the action table
                    // Production reduceOn = table.getProductions().get(reduce.productionId);
                    String arrowLabel = "default";
                    // arrowLabel += (" by prod " + reduceOn.toString());
                    arrowLabel = arrowLabel.replace("<", "&lt;");
                    arrowLabel = arrowLabel.replace(">", "&gt;");

                    // int target = table.getGotoTable()[stateNo][reduceOn.getNonTerminal().getId()];
                    // reduce looks to the goto table of the state on top of stack, not
                    // the current state, hence, can never be rendered to graph ..
                    int target = stateNo;
                    strArrow += ("lalr_" + stateNo + " -> " + "lalr_" + target + " [arrowhead = dot,label=\"" + arrowLabel + "\"];\n");
                }
            }

            for (int terminal = 0; terminal < table.getActionTableWidth();
                     terminal++)
            {
                if (table.getActionTable()[stateNo][terminal] != null) // not error
                {
                    if (table.getActionTable()[stateNo][terminal] instanceof Shift)
                    {
                        Shift shift = (Shift)table.getActionTable()[stateNo][terminal];
                        String arrowLabel = (table.getTerminals().get(terminal)).getName();
                        int goTo = shift.stateNumber;
                        strArrow += ("lalr_" + stateNo + " -> " + "lalr_" + goTo + " [label = \"" + arrowLabel + "\"];\n");
                    }
                    else if (table.getActionTable()[stateNo][terminal] instanceof Reduce && !defaultActionDetected)
                    {
                        Reduce reduce = (Reduce)table.getActionTable()[stateNo][terminal];

                        if ((table.getProductions().get(reduce.productionId)).getName() == null)
                        {
                            isAcceptingState = true;
                            thisGrammarCanAccept = true;
                            acceptingState = stateNo;
                        }

                        // the accepting "augmenting" state can't have goto actions
                        if ( !isAcceptingState)
                        {
                            // default action is at the last index of the action table
                            // Production reduceOn = table.getProductions().get(reduce.productionId);
                            String arrowLabel = (terminal == (table.getActionTable()[0].length - 1)) ? "default" : table.getTerminals().get(terminal).getName();
                            // arrowLabel += (" by prod " + reduceOn.toString());
                            arrowLabel = arrowLabel.replace("<", "&lt;");
                            arrowLabel = arrowLabel.replace(">", "&gt;");

                            // int target = table.getGotoTable()[stateNo][reduceOn.getNonTerminal().getId()];
                            // reduce looks to the goto table of the state on top of stack, not
                            // the current state, hence, can never be rendered to graph ..
                            int target = stateNo;
                            strArrow += ("lalr_" + stateNo + " -> " + "lalr_" + target + " [arrowhead = dot,label=\"" + arrowLabel + "\"];\n");
                        }
                    }
                }
            }

            // process the goto table
            for (int nonTerminal = 0; nonTerminal < table.getGoToTableWidth();
                     nonTerminal++)
            {
                if (table.getGotoTable()[stateNo][nonTerminal] != 0) // not error
                {
                    int gotoState = table.getGotoTable()[stateNo][nonTerminal] - 1; // restore
                                                                                    // value

                    String arrowLabel = (table.getNonTerminals().get(nonTerminal)).getName();
                    strArrow += ("lalr_" + stateNo + " -> " + "lalr_" + gotoState + " [arrowhead = empty, label = \"" + arrowLabel + "\"];\n");
                }
            }

            if ( !isAcceptingState)
                sb.append("lalr_" + stateNo + " [shape=none];\n");
            else
                sb.append("lalr_" + stateNo + " [shape=box];\n");

            sb.append("lalr_" + stateNo + " [label=<" + stateStr + ">];\n");
            sb.append(strArrow);
        }

        if ( !thisGrammarCanAccept)
        {
            System.out.println("ERR: this grammar cannot accept, it will never reduce to the start rule\n");
        }

        sb.append("{rank = source; lalr_0 }\n" + "{rank = sink; " + "lalr_" + acceptingState + "}\n");
        sb.append("}");

        return sb.toString();
    }

    public static String dumpDot(DFAState startState)
    {
        StringBuilder sb = new StringBuilder();
        sb.append("digraph dfa {\n");

        Queue<DFAState> queue = new LinkedList<DFAState>();
        Set<Integer> processed = new HashSet<Integer>();
        Set<Integer> accepting = new HashSet<Integer>(); // list of accepting states

        queue.offer(startState);
        processed.add(startState.getId());

        while ( !queue.isEmpty())
        {
            DFAState state = queue.remove();

            if (state.acceptingState)
            {
                accepting.add(state.getId());
                sb.append("dfa_" + state.getId() + " [shape=oval,peripheries=2];\n");
                sb.append("dfa_" + state.getId() + " [label=\"" + state.token + "/" + state.getId() + " " + state.getNfaIds() + "\"];\n");
            }
            else
            {
                sb.append("dfa_" + state.getId() + " [shape=oval];\n");
                sb.append("dfa_" + state.getId() + " [label=\"dfa_" + state.getId() + " " + state.getNfaIds() + "\"];\n");
            }

            // used to calculate ranges
            Map<DFAState, ArrayList<Character>> transToSameNode = getTransToSameNode(state.transitions);

            // process non e-trans only
            for (Map.Entry<DFAState, ArrayList<Character>> entry : transToSameNode.entrySet())
            {
                DFAState to = entry.getKey();

                SortedSet<Character> characters = new TreeSet<Character>(entry.getValue());

                if ( !processed.contains(to.getId()))
                {
                    queue.offer(to);
                    processed.add(to.getId());
                }

                if (characters.size() > 1)
                {
                    ArrayList<char[]> ranges = getRanges(characters);

                    String label = "";

                    // from "state" to "to"
                    for (char[] range : ranges)
                    {
                        label += (((label.length() == 0) ? "" : ", ") + ((range[0] == '\\' || range[0] == '"') ? "\\" + range[0] : range[0]));

                        if (range.length > 1)
                            label += (".." + ((range[1] == '\\' || range[1] == '"') ? "\\" + range[1] : range[1]));
                    }

                    sb.append("dfa_" + state.getId() + " -> " + "dfa_" + to.getId() + " [label = \"" + label + "\"];\n");
                }
                else
                    sb.append("dfa_" + state.getId() + " -> " + "dfa_" + to.getId() + " [label = \"" + ((characters.first() == '\\' || characters.first() == '"') ? "\\" + characters.first() : characters.first()) + "\"];\n");
            }
        }

        // sb.append("{rank = sink ");
        //
        // for (int i : accepting)
        // {
        // sb.append("; dfa_" + i + " ");
        // }
        //
        // sb.append("}");
        sb.append("}");

        return sb.toString();
    }

    public static String dumpDot(NFAState startState)
    {
        StringBuilder sb = new StringBuilder();
        sb.append("digraph nfa {\nrankdir=LR;\n");

        Queue<NFAState> queue = new LinkedList<NFAState>();
        Set<Integer> processed = new HashSet<Integer>();
        Set<Integer> accepting = new HashSet<Integer>(); // list of accepting states

        queue.offer(startState);
        processed.add(startState.getId());

        while ( !queue.isEmpty())
        {
            NFAState state = queue.remove();

            if (state.isAcceptable())
            {
                accepting.add(state.getId());
                sb.append("nfa_" + state.getId() + " [shape=doublecircle];\n");
                sb.append("nfa_" + state.getId() + " [label=\"" + state.getToken() + "/" + state.getId() + "\"];\n");
            }
            else
            {
                sb.append("nfa_" + state.getId() + " [shape=circle];\n");
            }

            // used to calculate ranges
            Map<NFAState, ArrayList<NFATransition>> transToSameNode = getNonEpsilonTransToSameNode(state.getTransitions());

            // process non e-trans only
            for (Map.Entry<NFAState, ArrayList<NFATransition>> entry : transToSameNode.entrySet())
            {
                NFAState to = entry.getKey();

                SortedSet<Character> characters = new TreeSet<Character>();

                for (NFATransition trans : entry.getValue())
                {
                    characters.add(trans.getCharacter());

                    for (NFAState s : trans.getDestinations())
                        if ( !processed.contains(s.getId()))
                        {
                            processed.add(s.getId());
                            queue.offer(s);
                        }
                }

                if (characters.size() > 1)
                {
                    // get ranges
                    ArrayList<char[]> ranges = getRanges(characters);

                    String label = "";

                    // from "state" to "to"
                    for (char[] range : ranges)
                    {
                        label += (((label.length() == 0) ? "" : ", ") + ((range[0] == '\\' || range[0] == '"') ? "\\" + range[0] : range[0]));

                        if (range.length > 1)
                            label += (".." + ((range[1] == '\\' || range[1] == '"') ? "\\" + range[1] : range[1]));
                    }

                    sb.append("nfa_" + state.getId() + " -> " + "nfa_" + to.getId() + " [label = \"" + label + "\"];\n");
                }
                else
                    sb.append("nfa_" + state.getId() + " -> " + "nfa_" + to.getId() + " [label = \"" + ((characters.first() == '\\' || characters.first() == '"') ? "\\" + characters.first() : characters.first()) + "\"];\n");
            }

            // process e-trans only
            for (NFATransition t : state.getTransitions())
            {
                if ( !(t instanceof ETransition))
                    continue;

                for (NFAState s : t.getDestinations())
                {
                    // output transition
                    // ... (if accepting change node shape )
                    sb.append("nfa_" + state.getId() + " -> " + "nfa_" + s.getId() + " [label = \"EP\"];\n");

                    if ( !processed.contains(s.getId()))
                    {
                        processed.add(s.getId());
                        queue.offer(s);
                    }
                }
            }
        }

        sb.append("{rank = sink ");

        for (int i : accepting)
        {
            sb.append("; nfa_" + i + " ");
        }

        sb.append("}");
        sb.append("}");

        return sb.toString();
    }

    private static Map<NFAState, ArrayList<NFATransition>> getNonEpsilonTransToSameNode(ArrayList<NFATransition> transitions)
    {
        Map<NFAState, ArrayList<NFATransition>> ret = new HashMap<NFAState, ArrayList<NFATransition>>();

        for (NFATransition t : transitions)
        {
            if ( !(t instanceof ETransition))
                for (NFAState state : t.getDestinations())
                {
                    if (ret.get(state) == null)
                        ret.put(state, new ArrayList<NFATransition>());

                    ret.get(state).add(t);
                }
        }

        return ret;
    }

    private static ArrayList<char[]> getRanges(SortedSet<Character> characters)
    {
        // get ranges
        char first = characters.first();
        char last = characters.first();
        ArrayList<char[]> ranges = new ArrayList<char[]>(); // either [1] or [2] for single isolated char or range

        for (Character c : characters.tailSet((char)(last + 1)))
        {
            if (c != (char)(last + 1))
            {
                if (first != last)
                {
                    ranges.add(new char[]{first, last});
                }
                else
                {
                    ranges.add(new char[]{last});
                }

                first = c;
            }

            last = c;
        }

        if (first != last)
        {
            // cuz last character can't be handled inside the loop
            ranges.add(new char[]{first, last});
        }
        else
        {
            ranges.add(new char[]{last});
        }

        return ranges;
    }

    private static Map<DFAState, ArrayList<Character>> getTransToSameNode(Map<Character, DFAState> transitions)
    {
        Map<DFAState, ArrayList<Character>> ret = new HashMap<DFAState, ArrayList<Character>>();

        for (Map.Entry<Character, DFAState> t : transitions.entrySet())
        {
            if (ret.get(t.getValue()) == null)
                ret.put(t.getValue(), new ArrayList<Character>());

            ret.get(t.getValue()).add(t.getKey());
        }

        return ret;
    }

    public static String dumpDot(DFA dfa)
    {
        StringBuilder sb = new StringBuilder();
        sb.append("digraph dfa {\n");

        for (int state = /* 1 */0; state < dfa.stateBySymbolToState.length; state ++ )
        {
            if ( !dfa.isAnyFinalStateReachableFrom(state) || !dfa.isStateReachableFromStartState(state))
                continue;

            String shape = "oval";
            if (state == dfa.startingState)
                shape = "rectangle";
            if (Arrays.binarySearch(dfa.acceptingStates, state) >= 0)
            {
                sb.append("dfa_" + state + " [shape=" + shape + ",peripheries=2];\n");
                sb.append("dfa_" + state + " [label=\"" + state + "\"];\n");
            }
            else
            {

                sb.append("dfa_" + state + " [shape=" + shape + "];\n");
                sb.append("dfa_" + state + " [label=\"" + state + "\"];\n");
            }

            for (int symbol = 0; symbol < dfa.symbol.length; symbol ++ )
            {
                // if (dfa.stateBySymbolToState[state][symbol] != 0)
                {
                    int target = dfa.stateBySymbolToState[state][symbol];
                    if (dfa.isAnyFinalStateReachableFrom(target))
                        sb.append("dfa_" + state + " -> " + "dfa_" + target + " [label = \"" + dfa.symbol[symbol] + "\"];\n");
                }
            }
        }

        // sb.append("{rank = sink ");
        //
        // for (int i : accepting)
        // {
        // sb.append("; dfa_" + i + " ");
        // }
        //
        // sb.append("}");
        sb.append("}");

        return sb.toString();
    }
}
